# 58/100 回溯-组合总和
# leetcode第46题: https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/4

from leetcode import test


def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    res = []

    def backtracking(path: list[int], start: int, cur_sum: int):
        if cur_sum == target:
            res.append(path[:])
            return
        elif cur_sum > target:
            return
        for i, x in enumerate(candidates):
            if i >= start:
                path.append(x)
                cur_sum += x
                backtracking(path, i, cur_sum)
                path.pop()
                cur_sum -= x

    backtracking([], 0, 0)
    return res


if __name__ == '__main__':
    inp = [{"candidates": [2, 3, 6, 7], "target": 7},
           {"candidates": [2, 3, 5], "target": 8},
           {"candidates": [2], "target": 1}, ]

    out = [
        [[2, 2, 3], [7]],
        [[2, 2, 2, 2], [2, 3, 3], [3, 5]],
        []
    ]

    test.test_function(combinationSum, inp, out)
